\documentclass{article}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{float}
\usepackage{tabularx}
\usepackage[usenames,dvipsnames]{color} % For colors and names
\usepackage{multirow}
\usepackage{amsmath}
\hyphenpenalty=1115000

\newcommand{\specialcell}[2][c]{%
  \begin{tabular}[#1]{@{}c@{}}#2\end{tabular}}


\title{\textbf{Metody sztucznej inteligencji 12L} \\ Raport końcowy} % Title

\author{Tomasz \textsc{Bawej} \\ Łukasz \textsc{Trzaska}} % Author name

\definecolor{mygrey}{gray}{.96} % Light Grey
\lstset{language=Verilog, tabsize=3, backgroundcolor=\color{mygrey}, basicstyle=\small, commentstyle=\color{BrickRed}}
\lstset{ 
	language=[ISO]C++,              % choose the language of the code ("language=Verilog" is popular as well)
   	tabsize=3,							  % sets the size of the tabs in spaces (1 Tab is replaced with 3 spaces)
	basicstyle=\scriptsize,               % the size of the fonts that are used for the code
	numbers=left,                   % where to put the line-numbers
	numberstyle=\scriptsize,              % the size of the fonts that are used for the line-numbers
	stepnumber=2,                   % the step between two line-numbers. If it's 1 each line will be numbered
	numbersep=5pt,                  % how far the line-numbers are from the code
	backgroundcolor=\color{mygrey}, % choose the background color. You must add \usepackage{color}
	%showspaces=false,              % show spaces adding particular underscores
	%showstringspaces=false,        % underline spaces within strings
	%showtabs=false,                % show tabs within strings adding particular underscores
	frame=single,	                 % adds a frame around the code
	captionpos=b,                   % sets the caption-position to bottom
	breaklines=true,                % sets automatic line breaking
	breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
	%escapeinside={\%*}{*)},        % if you want to add a comment within your code
	commentstyle=\color{BrickRed}   % sets the comment style
}
\usepackage{titlesec}
\titleformat{\section}{\large\bfseries}{\thesection}{1em}{}
\newenvironment{packed_enum}{
\begin{enumerate}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{enumerate}}

\begin{document}

\maketitle % Insert the title, author and date

\setlength\parindent{0pt} % Removes all indentation from paragraphs

\section{Treść zadania} (Grupa W1.)
\textbf {SB3. rak płuc.} Zaprojektować i wykonać system wnioskowania służący do wspomagania decyzji w diagnozie raka płuc. Do realizacji zadania zostanie wykorzystane środowisko MatLab wraz z biblioteką BNT (\textit{Bayes Net Toolbox}) oraz \textbf{GeNIe\&Smile}.
\section{Analiza problemu}
\paragraph*{Dane.} W danych do zadanego problemu decyzyjnego wyszczególniono 11 zmiennych losowych, oznaczających odpowiednio albo czynniki chorobotwórcze albo symptomy choroby. Są one boolowskie (binarne), z interpretacją istnienia/nieistnienia czynnika lub symptomu.\\Zmienna celu reprezentowana jest przez wartości -1 (nie wykryto choroby) bądź 1 (wykryto). Na rysunku poniżej zaprezentowano statystykę stosunku liczby wartości zmiennej docelowej.
\begin{figure}[H]
\hspace*{0in}
\caption{Statystyka wartości zmiennej docelowej \textit{cancer$\{-1,1\}$} wygenerowana przez Genie\&Smile}
\centering
\includegraphics[width=80mm]{gen-cancer-stat.jpg}
\label{fig1}
\end{figure}
\paragraph*{Identyfikacja zależności zmiennych.} Posiadając wiedzę ekspercką, problemu tego nie ma - można od razu zidentyfikować zależności przyczynowo skutkowe w grafie Bayesowskim (Wariant 1). Bez takiej wiedzy zależności te muszą być wykryte jedynie na podstawie danych trenujących (Wariant 2). Na rysunku poniżej zaprezentowano macierz korelacji dla zmiennych obliczoną przez pakiet Genie\&Smile. 
\linebreak
\begin{figure}[H]
\hspace*{-1.5in}
\caption{Macierz korelacji zmiennych wygenerowana przez Genie\&Smile}
\includegraphics[width=150mm]{gen-correl.jpg}
\label{fig2}
\end{figure}
\paragraph*{Określenie prawdopodobieństw warunkowych na podstawie eksperymentu.} Rozkład prawdopodobieństwa dla zmiennych losowych jest tutaj explicite nieznany.\\
W fazie uaktualnienia sieci, na chwilę obecną, algorytm do uaktualniania jest dla autorów rozwiązania nie w pełni nieznany. Wiadomo jedynie, że algorytmy aproksymujące wartości, które zapewne będą wykorzystane to: (ang.) \textit{probabilistic logic sampling}, \textit{likelihood sampling}, \textit{backward sampling}, \textit{adaptive importance sampling} (AIS-BN) i \textit{approximate posterior importance sampling} (APIS-BN).
\section{Algorytm  rozwiązania i koncepcja struktury}
\paragraph*{Dla Wariantu 2.} (bez wiedzy eksperckiej), istnieją najogólniej biorąc, dwa podejścia do nauki "struktury" grafu: bazująca na ograniczeniach (ang. \textit{constraint-based}) oraz wyszukiwania i oceny (ang. \textit{search-and-score}).\\
Oba narzędzia udostępniają opcję uczenia się struktury (ang. \textit{structure learning}). Do tego zadania w GeNIe\&Smile dostępne są algorytmy: \textit{bayesian search}, \textit{PC}, przeszukiwanie grafu, \textit{greedy thick-thinning}, \textit{naive bayes} oraz \textit{tree augmented bayes}. BNT udostępnia natomiast: \textit{hill climbing}, K2, \textit{Markov chain}, \textit{Monte Carlo}, PC, \textit{structural EM} oraz przeszukiwanie \textit{brute-force}.
\paragraph*{Struktura na podstawie wiedzy eksperckiej.} W odniesieniu do danych o charakterze binarnym z jakimi mamy do czynienia w zadnaniu, odpowiadające im węzły grafu będą etykietowane wprost nazwami poszczególnych zmiennych losowych. Struktura sieci skonstruowana na podstawie wiedzy eksperckiej przedstawiona jest na poniższym obrazie:\\
\begin{figure}[H]
\includegraphics[width=120mm]{gen-cancer-expert-struct.jpg}
\centering
\caption{Proponowana struktura sieci oparta na wiedzy eksperckiej w Genie\&Smile}
\label{fig2}
\end{figure}
\section{Zakres wykorzystania funkcjonalności programów}
\paragraph*{Programy zostały użyte} zarówno do odnalezienia zależności między zmiennymi, uaktualnienia sieci poprzez wprowadzenie danych oraz pokazania działania sieci.  
Do przekształcenia danych, w przypadku pakietu MatLab jest to na pewno możliwe. Jeżeli pakiet GeNIe nie udostępnia takiej opcji, to podjęta zostanie próba "przycięcia" danych w MatLab dla obu programów.
\section{Genie\&Smile}
Pakiet Genie\&Smile zachęcał interfejsem użytkownika i działał płynnie. Obok oczywistych funkcjonalności łatwej budowy sieci przy użyciu GUI oraz automatycznego na podstawie danych, Genie udostępnia praktyczny i czytelny zestaw funkcji do tworzenia ogólnych statystyk zmiennych oraz tablicę korelacji między nimi. Jedyne co można mu zarzucić to brak możliwości łatwego modyfikowania  danych (u nas wycinania części przykładów). Braki te uzupełniono użyciem pakietu MatLab.
\paragraph*{Struktura na bazie wiedzy eksperckiej} jak zaprezentowano na Rysunku 1, została do badań wykorzystana najpierw. Oto wyniki:
Odpytywanie sieci uczonej \textbf{danymi pełnymi.} Po ustawieniu \textit{evidence} (stałych wartości dla pewnych zmiennych losowych) sieć zwróciła następujące wyniki (\textit{Pr} - oznacza prawdopodobieństwo)
\begin{enumerate}
\item[-] dla nieustawionej żadnej wartości $Pr(cancer=1)=0.72$
\item[I.] dla $fatigue = 1$ oraz $coughing = 1$ wartość $Pr(cancer=1)=0.89$
\item[II.] dla $fatigue = 0$ oraz $coughing = 1$ wartość $Pr(cancer=1)=0.73$
\item[III.] dla $fatigue = 1$ oraz $coughing = 0$ wartość $Pr(cancer=1)=0.43$

\item[IV.] dla nieustawionych żadnych wartości $Pr(car\_accident=1)=0.72$
\item[V.] dla $smoking = 1$ oraz $attention\_disorder = 1$ wartość $Pr(car\_accident=1)=0.93$
\item[VI.] dla $smoking = 1$ oraz $attention\_disorder = 0$ wartość $Pr(car\_accident=1)=0.66$
\item[VII.] dla $smoking = 0$ oraz $attention\_disorder = 0$ wartość $Pr(car\_accident=1)=0.55$
\end{enumerate}
Odpytywanie sieci uczonej \textbf{danymi niekompletnymi.} Sieć zwróciła następujące wyniki:
\begin{enumerate}
\item[-] dla nieustawionej żadnej wartości $Pr(cancer=1)=0.72$
\item[I.] dla $fatigue = 1$ oraz $coughing = 1$ wartość $Pr(cancer=1)=0.89$
\item[II.] dla $fatigue = 0$ oraz $coughing = 1$ wartość $Pr(cancer=1)=0.70$
\item[III.] dla $fatigue = 1$ oraz $coughing = 0$ wartość $Pr(cancer=1)=0.30$

\item[IV.] dla nieustawionych żadnych wartości $Pr(car\_accident=1)=0.73$
\item[V.] dla $smoking = 1$ oraz $attention\_disorder = 1$ wartość $Pr(car\_accident=1)=0.94$
\item[VI.] dla $smoking = 1$ oraz $attention\_disorder = 0$ wartość $Pr(car\_accident=1)=0.67$
\item[VII.] dla $smoking = 0$ oraz $attention\_disorder = 0$ wartość $Pr(car\_accident=1)=0.54$
\end{enumerate}

\paragraph*{Struktura sieci wywnioskowana automatycznie} z danych przez Genie\&Smile algorytmem PS (max adjacency size: 8, Significance level: 0,05, Czas nieograniczony). 
\begin{figure}[H]
\includegraphics[width=120mm]{gen-cancer-learn-struct-1-PS.jpg}
\centering
\caption{Struktura sieci wywnioskowana automatycznie z danych przez Genie\&Smile algorytmem PS}
\label{fig3}
\end{figure}
Odpytywanie \textbf{sieci uczonej danymi pełnymi}. Po ustawieniu \textit{evidence} sieć zwróciła następujące wyniki (\textit{Pr} - oznacza prawdopodobieństwo)
\begin{enumerate}
\item[-] dla nieustawionej żadnej wartości $Pr(cancer=1)=0.72$
\item[I.] dla $fatigue = 1$ oraz $coughing = 1$ wartość $Pr(cancer=1)=0.90$
\item[II.] dla $fatigue = 0$ oraz $coughing = 1$ wartość $Pr(cancer=1)=0.46$
\item[III.] dla $fatigue = 1$ oraz $coughing = 0$ wartość $Pr(cancer=1)=0.46$

\item[IV.] dla nieustawionych żadnych wartości $Pr(car\_accident=1)=0.72$
\item[V.] dla $smoking = 1$ oraz $attention\_disorder = 1$ wartość $Pr(car\_accident=1)=0.93$
\item[VI.] dla $smoking = 1$ oraz $attention\_disorder = 0$ wartość $Pr(car\_accident=1)=0.66$
\item[VII.] dla $smoking = 0$ oraz $attention\_disorder = 0$ wartość $Pr(car\_accident=1)=0.55$
\end{enumerate}
Odpytywanaie sieci uczonej \textbf{danymi niekompletnymi.} Usunięto 10\% wartości z losowych wierszy w losowo wybranych kolumnach, czego dokonano przy użyciu Genie\&Smile. Wyniki zwrócone przez sieć w tej sytuacji:
\begin{enumerate}
\item[-] dla nieustawionej żadnej wartości $Pr(cancer=1)=0.74$
\item[I.] dla $fatigue = 1$ oraz $coughing = 1$ wartość $Pr(cancer=1)=0.88$
\item[II.] dla $fatigue = 0$ oraz $coughing = 1$ wartość $Pr(cancer=1)=0.71$
\item[III.] dla $fatigue = 1$ oraz $coughing = 0$ wartość $Pr(cancer=1)=0.32$

\item[IV.] dla nieustawionych żadnych wartości $Pr(car\_accident=1)=0.71$
\item[V.] dla $smoking = 1$ oraz $attention\_disorder = 1$ wartość $Pr(car\_accident=1)=0.91$
\item[VI.] dla $smoking = 1$ oraz $attention\_disorder = 0$ wartość $Pr(car\_accident=1)=0.64$
\item[VII.] dla $smoking = 0$ oraz $attention\_disorder = 0$ wartość $Pr(car\_accident=1)=0.54$
\end{enumerate}
\section{MatLab\&BNT}
\begin{figure}[H]
\hspace*{-1in}
\caption{Wywnioskowana przez MatLab BNT struktura sieci}
\centering
\includegraphics[width=\linewidth]{bnt_discovered_net.png}
\label{fig1}
\end{figure}

Poniżej zebrano wyniki uzyskane przy użyciu pakietu BNT oraz powtórzono, celem porównania, rezultaty zanotowane dla~Genie. Etykiety wierszy należy interpretować jako $P(licznik|mianownik)$. Kolejne kolumny zawierają wartości odpowiednich prawdopodobieństw obliczonych przy użyciu obu programów oraz dla różnych scenariuszy uczenia sieci.

Strukturę sieci generowaną na podstawie danych otrzymano z użyciem algorytmu \textit{Markov Chain Monte Carlo}, podczas gdy do wyznaczania parametrów sieci budowanej w oparciu o niekompletne dane wykorzystano algorytm \textit{EM}.  

\begin{table}[h!]\footnotesize
\caption{Zestawienie porównawcze wybranych prawdopodobieństw obliczonych przy wykorzystaniu obu programów}
\renewcommand{\arraystretch}{1.8}
\begin{tabularx}{\textwidth}{|c|X|X|X|X|X|X|}
\hline
& 
\multicolumn{2}{c|}{\specialcell{Sieć ekspercka,\\kompletne dane}} &
\multicolumn{2}{c|}{\specialcell{Sieć ekspercka,\\przesiane dane}} &
\multicolumn{2}{c|}{\specialcell{Sieć generowana,\\przesiane dane}} \\
\cline{2-7}
&Genie&BNT&Genie&BNT&Genie&BNT\\
\hline
\specialcell{$\dfrac{cancer}{coughing, fatigue}$ } 		& 0.89	& 0.89	& 0.89	& 0.89	& 0.90 & 0.90	\\
\hline
\specialcell{$\dfrac{cancer}{coughing, !fatigue}$ } 	& 0.73	& 0.73	& 0.70	& 0.73	& 0.70	& 0.74	\\
\hline
\specialcell{$\dfrac{cancer}{!coughing, fatigue}$ } 	& 0.43	& 0.47	& 0.30	& 0.47	& 0.46	& 0.46	\\
\hline
\specialcell{$\dfrac{cancer}{!coughing, !fatigue}$ }	& 0.29	& 0.29	&  0.30 &  0.29	& 0.30 & 0.28	\\
\hline

\specialcell{$\dfrac{carAccident}{(smoking, attentionDis.)}$} 	& 0.93	& 0.93	& 0.94 & 0.93 & 0.93	& 0.93 \\
\hline
\specialcell{$\dfrac{carAccident}{(smoking, !attentionDis.)}$}	& 0.66	& 0.66	& 0.67 & 0.66 & 0.66	& 0.66 \\
\hline
\specialcell{$\dfrac{carAccident}{(!smoking, attentionDis.)}$}	& 0.89 & 0.89 & 0.90 & 0.89	& 0.90 & 0.89 \\
\hline
\specialcell{$\dfrac{carAccident}{(!smoking, !attentionDis.)}$}	& 0.55 & 0.55 & 0.54 & 0.54	& 0.55 & 0.55 \\
\hline
\end{tabularx}
\end{table}

\pagebreak

\section{Porównanie Genie\&Smile z MatLab\&BNT}
\begin{table}[h]\footnotesize
\caption{Porównanie GenieSmile z MatLabBNT}
\begin{tabularx}{\textwidth}{ |X|X|X| }
  \hline
  \textbf{Cecha} & \textbf{Genie\&Smile} & \textbf{MatLab\&BNT} \\
  \hline
	\hline  
Dokumentacja & Czytelne samouczki. Sprzed 5 lat. & Mało czytelna, wszystko na jednej stronie. Sprzed 5 lat.\\
  \hline
  GUI & Wygodne sterowanie programem przy użyciu GUI, czytelna wizualizacja sieci. &  Sterowanie - jedynie konsola MatLab. Wizualizacja - rysowanie struktury sieci.\\
  \hline
  Operowanie na danych & Import z wielu źródeł, dyskretyzacja, generowanie danych. &  Wydajne, wrodzone w operacje na macierzach.\\
  \hline
  Szybkość działania (dla 2000 rekordów) & Ok 1. sek. &  Ok 1. sek.\\
  \hline
  Cena & Darmowe. &  Darmowe.\\
\hline  
  Operowanie na niepełnych danych & tak & tak
  \\
  \hline
  Dostępne algorytmy do szukania struktury & Bayesian Search, PC, Essential Graph Search, Greedy Thick Thinning, Tree Augmented Native Bayes & Markov Chain Monte Carlo, Hill Climbing, K2, Brute Force \\
  \hline
\end{tabularx}
\end{table}



\end{document}
